package com.cuz.series.linklist;

/****
 * https://leetcode.cn/problems/copy-list-with-random-pointer/
 */
public class 链表5复制包含随机节点的链表 {


    private static class Node {
        int val;
        Node next;
        Node random;

        public Node(int val) {
            this.val = val;
            this.next = null;
            this.random = null;
        }
    }

    private static void print(Node node) {
        String val = String.valueOf(node.val);
        String nextVal;
        if (node.next == null) {
            nextVal = val + "next null";
        } else {
            nextVal = String.valueOf(node.next.val);
        }
        String randomVal;
        if (node.random == null) {
            randomVal = val + "random null";
        } else {
            randomVal = String.valueOf(node.random.val);
        }
        String msg = String.format("val :%s,next :%s,randomVal :%s", val, nextVal, randomVal);
        System.out.println(msg);

        if (node.next != null) {
            print(node.next);
        }
    }

    private static void test() {
        //[[7,null],[13,0],[11,4],[10,2],[1,0]]
        Node node7 = new Node(7);
        Node node13 = new Node(13);
        Node node11 = new Node(11);
        Node node10 = new Node(10);
        Node node1 = new Node(1);

        node13.random = node7;
        node11.random = node1;
        node10.random = node11;
        node1.random = node7;

        node7.next = node13;
        node13.next = node11;
        node11.next = node10;
        node10.next = node1;
        print(node7);
        System.out.println("==============");
        Node node = copyRandom(node7);
        print(node);
    }

    public static void main(String[] args) {
        Node node = new Node(-1);
        node.random = node;
        Node node1 = copyRandom(node);
        print(node1);

    }

    public static Node copyRandom(Node node) {
        if (node == null) {
            return null;
        }
        //重复节点 1->2->3 变成1->1->2->2->3->3
        repeatLinkList(node);
        //连接复制节点的random 复制节点的random 等于复制源节点random.next
        linkRandom(node);
        //把复制源 和 复制结果分开
        return separateReturnNewHead(node);
    }

    private static Node separateReturnNewHead(Node node) {
        //复制后的头
        Node copyHead = node.next;

        //遍历
        while (node != null) {
            //当前节点的拷贝节点
            Node next1 = node.next;

            //下一步的节点
            Node next2 = node.next.next;
            //把复制节点连接断开
            node.next = next2;

            //复制节点和原节点断开
            if (next2 != null) {
                next1.next = next2.next;
            }
            //继续
            node = next2;
        }

        return copyHead;
    }

    private static void linkRandom(Node node) {
        //连接复制结果的random
        while (node != null) {
            //源节点
            Node source = node;
            //拷贝节点
            Node repeat = node.next;
            //源节点的random指向
            Node sourceRandom = source.random;
            //npe check
            if (sourceRandom != null) {
                //复制节点的random 等于源节点random的下一个节点
                repeat.random = sourceRandom.next;
            }
            //继续
            node = node.next.next;
        }
    }

    private static void repeatLinkList(Node node) {

        //重复节点
        while (node != null) {
            Node next = node.next;
            //复制值
            Node repeat = new Node(node.val);
            //复制next 但是没有复制random
            repeat.next = next;
            node.next = repeat;
            node = next;
        }
    }

}
